Skip to main content

Non-overlapping Intervals

Question​

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example 1
Sample Input:
Intervals: [[1,2],[2,3],[3,4],[1,3]]

Sample Output:
[[1,2], [3,4]]

Solution​

all//Non-overlapping Intervals.py


def nonOverlappingIntervals(intervals):

    # Sort intervals in increasing order of
    # start time
    intervals.sort(key=lambda x: x[0])

    # Initialize the result
    result = [intervals[0]]

    # Start traversing intervals
    for i in range(1, len(intervals)):

        # If current interval doesn't overlap
        # with previous, add it to result
        if result[-1][1] < intervals[i][0]:
            result.append(intervals[i])

    return result

# Driver program
intervals = [[1,3], [2,4], [5,7], [6,8]]
print(nonOverlappingIntervals(intervals))